package uestc.lj.basicPromotion.tree;

/**
 * @Author:Crazlee
 * @Date:2021/11/29
 */
public class AbstractSelfBalancingBinarySearchTree extends AbstractBinarySearchTree {
	/**
	 * Rotate to the left.
	 *
	 * @param node Node on which to rotate.
	 * @return Node that is in place of provided node after rotation.
	 */
	protected Node rotateLeft(Node node) {
		Node temp = node.right;
		temp.parent = node.parent;

		node.right = temp.left;
		if (node.right != null) {
			node.right.parent = node;
		}

		temp.left = node;
		node.parent = temp;

		// temp took over node's place so now its parent should point to temp
		if (temp.parent != null) {
			if (node == temp.parent.left) {
				temp.parent.left = temp;
			} else {
				temp.parent.right = temp;
			}
		} else {
			root = temp;
		}

		return temp;
	}

	/**
	 * Rotate to the right.
	 *
	 * @param node Node on which to rotate.
	 * @return Node that is in place of provided node after rotation.
	 */
	protected Node rotateRight(Node node) {
		Node temp = node.left;
		temp.parent = node.parent;

		node.left = temp.right;
		if (node.left != null) {
			node.left.parent = node;
		}

		temp.right = node;
		node.parent = temp;

		// temp took over node's place so now its parent should point to temp
		if (temp.parent != null) {
			if (node == temp.parent.left) {
				temp.parent.left = temp;
			} else {
				temp.parent.right = temp;
			}
		} else {
			root = temp;
		}

		return temp;
	}

}
